πŸ‘©β€πŸ’» 92343. μ–‘κ³Ό λŠ‘λŒ€

@Seongukbaek Posted July 14, 2022 Β· Updated July 14, 2022 Β· 4 min read

문제

Programmers - μ–‘κ³Ό λŠ‘λŒ€

πŸ“ Logic

private ArrayList<Integer> makeList(ArrayList<Integer> nowNodeList, int nowN, int nextNode) { // 이동할 수 μžˆλŠ” λ…Έλ“œλ₯Ό μ €μž₯ν•  리슀트 ArrayList<Integer> nextList = new ArrayList<>(); // λ‹€μŒ λ…Έλ“œμ—μ„œ 갈 수 μžˆλŠ” λ…Έλ“œλ₯Ό μ €μž₯, μ—°κ²°λœ μžμ‹ λ…Έλ“œμ— λŒ€ν•΄μ„œλ§Œ! for (int fromNextNode : infoList.get(nextNode)) nextList.add(fromNextNode); // ν˜„ λ…Έλ“œκΉŒμ§€ μ˜€λŠ”λ° λ°©λ¬Έν–ˆλ˜ λ…Έλ“œλ“€ 쀑 ν˜„ λ…Έλ“œμ™€ 직전에 λ°©λ¬Έν•œ λ…Έλ“œλ₯Ό μ œμ™Έν•˜κ³  μ €μž₯, DFS둜 λ”°μ§€λ©΄ λ°±νŠΈλž˜ν‚Ήν•˜λŠ” λŠλ‚Œ.. for (int checkNode : nowNodeList) if (checkNode != nowN && checkNode != nextNode) nextList.add(checkNode); return nextList; }
  • ν˜„ λ…Έλ“œμ—μ„œ 갈 수 μžˆλŠ” λ…Έλ“œ 리슀트λ₯Ό μƒμ„±ν•˜λŠ” ν•¨μˆ˜
  • μ—°κ²°λœ μžμ‹ λ…Έλ“œλ‘œλ§Œ 이동할 수 μžˆλŠ” 게 μ•„λ‹ˆλΌ, μ§€λ‚˜μ™”λ˜ λ…Έλ“œ λ˜ν•œ 재방문 κ°€λŠ₯ν•˜κΈ°μ— 두 번째 λ°˜λ³΅λ¬Έμ—μ„œ 이λ₯Ό μ²˜λ¦¬ν•œλ‹€.

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
import java.util.*; class Node { int num; int sheepCount; int wolfCount; // 갈 수 μžˆλŠ” λ…Έλ“œλ₯Ό μ €μž₯ν•˜λŠ” 리슀트! ArrayList<Integer> list; public Node(int num, int sheepCount, int wolfCount, ArrayList<Integer> list) { this.num = num; this.sheepCount = sheepCount; this.wolfCount = wolfCount; this.list = list; } } class Solution { static ArrayList<ArrayList<Integer>> infoList; static int[] info; public int solution(int[] info, int[][] edges) { init(info.length, edges); this.info = info; return bfs(); } private void init(int length, int[][] edges) { infoList = new ArrayList<>(); for (int i = 0; i < length; i++) infoList.add(new ArrayList<>()); for (int[] edge : edges) { int n1 = edge[0]; int n2 = edge[1]; infoList.get(n1).add(n2); } } private int bfs() { Queue<Node> queue = new LinkedList<>(); queue.add(new Node(0, 1, 0, infoList.get(0))); int max = 0; while(!queue.isEmpty()) { Node now = queue.poll(); int nowN = now.num; int sheepCount = now.sheepCount; int wolfCount = now.wolfCount; ArrayList<Integer> nowNodeList = now.list; if (max < sheepCount) max = sheepCount; // ν˜„ λ…Έλ“œμ—μ„œ 갈 수 μžˆλŠ” λ…Έλ“œμ— λŒ€ν•΄ 확인 // nowN = 0, nextNode = {1, 8}, fromNextNode = {{2, 4}, {7, 9}} for (int nextNode : nowNodeList) { // μ–‘μ΄κ±°λ‚˜, λŠ‘λŒ€μ˜ μˆ˜κ°€ μ–‘μ˜ μˆ˜λ³΄λ‹€ 적은 경우 if (info[nextNode] == 0) queue.add(new Node(nextNode, sheepCount + 1, wolfCount, makeList(nowNodeList, nowN, nextNode))); else if (wolfCount + 1 < sheepCount) queue.add(new Node(nextNode, sheepCount, wolfCount + 1, makeList(nowNodeList, nowN, nextNode))); } } return max; } private ArrayList<Integer> makeList(ArrayList<Integer> nowNodeList, int nowN, int nextNode) { // 이동할 수 μžˆλŠ” λ…Έλ“œλ₯Ό μ €μž₯ν•  리슀트 ArrayList<Integer> nextList = new ArrayList<>(); // λ‹€μŒ λ…Έλ“œμ—μ„œ 갈 수 μžˆλŠ” λ…Έλ“œλ₯Ό μ €μž₯, μ—°κ²°λœ μžμ‹ λ…Έλ“œμ— λŒ€ν•΄μ„œλ§Œ! for (int fromNextNode : infoList.get(nextNode)) nextList.add(fromNextNode); // ν˜„ λ…Έλ“œκΉŒμ§€ μ˜€λŠ”λ° λ°©λ¬Έν–ˆλ˜ λ…Έλ“œλ“€ 쀑 ν˜„ λ…Έλ“œμ™€ 직전에 λ°©λ¬Έν•œ λ…Έλ“œλ₯Ό μ œμ™Έν•˜κ³  μ €μž₯, DFS둜 λ”°μ§€λ©΄ λ°±νŠΈλž˜ν‚Ήν•˜λŠ” λŠλ‚Œ.. for (int checkNode : nowNodeList) if (checkNode != nowN && checkNode != nextNode) nextList.add(checkNode); return nextList; } }

✏️ Review

  • μ²˜μŒμ—λŠ” DFS둜 ν•΄κ²°ν•΄μ•Ό ν•˜λ‚˜ 생각해보닀가, λ­”κ°€ BFS둜 풀어보고 μ‹Άμ—ˆκ³ , μ–‘μ˜ μˆ˜μ™€ λŠ‘λŒ€μ˜ μˆ˜μ— 따라 μ›λž˜λŠ” λͺ» κ°”λ˜ λ…Έλ“œλΌλ„ λ‹€μ‹œ 갈 수 μžˆλŠ” κ²½μš°κ°€ λ°œμƒν•˜κΈ°μ— μΌμ’…μ˜ λ°±νŠΈλž˜ν‚Ή κ΅¬ν˜„μ΄ ν•„μš”ν–ˆλ‹€.

    • μ•„μ΄λ””μ–΄λŠ” μž‘μ„ 수 μžˆμ—ˆμœΌλ‚˜, λ‹€μ‹œ λ°©λ¬Έν•΄μ•Ό ν•˜λŠ” κ²½μš°μ— λŒ€ν•œ κ΅¬ν˜„μ— μžˆμ–΄μ„œλŠ” μ°Έκ³ κ°€ ν•„μš”ν–ˆλ‹€...
    • μ°Έκ³ λ₯Ό 보고 λ‚˜μ„œ, 이런 μ‘μš© 문제λ₯Ό μ‹œκ°„ μ•ˆμ— ν’€μ–΄μ•Ό λ°•μ‚΄λ‚Ό 수 μžˆμ§€ μ•Šμ„κΉŒ .. ν•˜λŠ” 생각 ...
@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€